package practice6;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Dijkstra求最短路径模板
 */
public class Ac849 {

    static int n;
    static int m;
    static int INF=(int)1e9;
    static int[][] g=new int[1010][1010];       //存储有向图
    static int[] dist=new int[1010];      //存储每个点到1号点的距离
    static boolean[] st=new boolean[1010];    //存储该节点是否访问过

    public static void initGraph(){
        for(int i=0;i< g.length;i++){
            Arrays.fill(g[i],INF);
        }
    }

    public static int dijkstra(){
        Arrays.fill(dist,INF);
        dist[1]=0;
        for(int i=0;i<n-1;i++){     //遍历除起点外的其余点(n-1个)
            int t=-1;
            //找出距离起点最近的点,标记为t
            for(int j=1;j<=n;j++){
                if(!st[j] && (t==-1||dist[j]<dist[t])){     //未访问过且距离更短
                    t=j;
                }
            }
            st[t]=true;     //标记找出的最近点为true
            //更新其邻居的距离
            for(int j=1;j<=n;j++){
                dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
            }
        }
        if(dist[n]==INF){
            return -1;
        }
        return dist[n];
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        initGraph();        //初始化
        while(m-->0){
            int x=sc.nextInt();
            int y=sc.nextInt();
            int z=sc.nextInt();
            g[x][y]=z;
        }
        int ans = dijkstra();
        System.out.println(ans);
    }
}
